1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.cache;
18
19 import static com.google.common.base.Objects.firstNonNull;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.base.Preconditions.checkState;
22
23 import com.google.common.base.Equivalence;
24 import com.google.common.base.Ticker;
25 import com.google.common.cache.AbstractCache.StatsCounter;
26 import com.google.common.collect.ImmutableMap;
27 import com.google.common.util.concurrent.ExecutionError;
28 import com.google.common.util.concurrent.UncheckedExecutionException;
29
30 import java.util.AbstractSet;
31 import java.util.Collection;
32 import java.util.HashMap;
33 import java.util.Iterator;
34 import java.util.LinkedHashMap;
35 import java.util.Map;
36 import java.util.Map.Entry;
37 import java.util.NoSuchElementException;
38 import java.util.Set;
39 import java.util.concurrent.Callable;
40 import java.util.concurrent.ConcurrentMap;
41 import java.util.concurrent.ExecutionException;
42
43 import javax.annotation.Nullable;
44
45
46
47
48
49
50
51
52
53 public class LocalCache<K, V> implements ConcurrentMap<K, V> {
54 private static final int UNSET_INT = CacheBuilder.UNSET_INT;
55
56 private final LinkedHashMap<K, Timestamped<V>> cachingHashMap;
57 private final CacheLoader<? super K, V> loader;
58 private final RemovalListener removalListener;
59 private final StatsCounter statsCounter;
60 private final Ticker ticker;
61 private final long expireAfterWrite;
62 private final long expireAfterAccess;
63
64 LocalCache(CacheBuilder<? super K, ? super V> builder, CacheLoader<? super K, V> loader) {
65 this.loader = loader;
66 this.removalListener = builder.removalListener;
67 this.expireAfterAccess = builder.expireAfterAccessNanos;
68 this.expireAfterWrite = builder.expireAfterWriteNanos;
69 this.statsCounter = builder.getStatsCounterSupplier().get();
70
71
72 final long maximumSize = builder.maximumSize;
73 this.cachingHashMap = new CapacityEnforcingLinkedHashMap<K, V>(
74 builder.getInitialCapacity(),
75 0.75f,
76 (builder.maximumSize != UNSET_INT),
77 builder.maximumSize,
78 statsCounter,
79 removalListener);
80
81 this.ticker = firstNonNull(builder.ticker, Ticker.systemTicker());
82 }
83
84 @Override
85 public int size() {
86 return cachingHashMap.size();
87 }
88
89 @Override
90 public boolean isEmpty() {
91 return cachingHashMap.isEmpty();
92 }
93
94 @Override
95 public V get(Object key) {
96 key = checkNotNull(key);
97 Timestamped<V> value = cachingHashMap.get(key);
98
99 if (value == null) {
100 statsCounter.recordMisses(1);
101 return null;
102 } else if (!isExpired(value)) {
103 statsCounter.recordHits(1);
104 value.updateTimestamp();
105 return value.getValue();
106 } else {
107 statsCounter.recordEviction();
108 statsCounter.recordMisses(1);
109 alertListenerIfPresent(key, value.getValue(), RemovalCause.EXPIRED);
110 cachingHashMap.remove(key);
111 return null;
112 }
113 }
114
115 @Override
116 public V put(K key, V value) {
117 key = checkNotNull(key);
118 value = checkNotNull(value);
119 Timestamped<V> oldValue = cachingHashMap.put(key, new Timestamped<V>(value, ticker));
120 if (oldValue == null) {
121 return null;
122 }
123 alertListenerIfPresent(key, oldValue.getValue(), RemovalCause.REPLACED);
124 return oldValue.getValue();
125 }
126
127 @Override
128 public V remove(Object key) {
129 Timestamped<V> stamped = cachingHashMap.remove(key);
130 if (stamped != null) {
131 V value = stamped.getValue();
132
133 if (!isExpired(stamped)) {
134 alertListenerIfPresent(key, value, RemovalCause.EXPLICIT);
135 return value;
136 }
137
138 alertListenerIfPresent(key, value, RemovalCause.EXPIRED);
139 }
140 return null;
141 }
142
143 @Override
144 public void putAll(Map<? extends K, ? extends V> m) {
145 for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
146 put(entry.getKey(), entry.getValue());
147 }
148 }
149
150 @Override
151 public void clear() {
152 if (removalListener != null) {
153 for (Map.Entry<K, Timestamped<V>> entry : cachingHashMap.entrySet()) {
154 alertListenerIfPresent(entry.getKey(), entry.getValue().getValue(), RemovalCause.EXPLICIT);
155 }
156 }
157 cachingHashMap.clear();
158 }
159
160 @Override
161 public V putIfAbsent(K key, V value) {
162 V currentValue = get(key);
163 if (currentValue != null) {
164 return currentValue;
165 }
166 return put(key, value);
167 }
168
169 @Override
170 public boolean remove(Object key, Object value) {
171 if (value.equals(get(key))) {
172 alertListenerIfPresent(key, value, RemovalCause.EXPLICIT);
173 remove(key);
174 return true;
175 }
176 return false;
177 }
178
179 @Override
180 public boolean replace(K key, V oldValue, V newValue) {
181 if (oldValue.equals(get(key))) {
182 alertListenerIfPresent(key, oldValue, RemovalCause.REPLACED);
183 put(key, newValue);
184 return true;
185 }
186 return false;
187 }
188
189 @Override
190 public V replace(K key, V value) {
191 V currentValue = get(key);
192 if (currentValue != null) {
193 alertListenerIfPresent(key, currentValue, RemovalCause.REPLACED);
194 return put(key, value);
195 }
196 return null;
197 }
198
199 @Override
200 public boolean containsKey(Object key) {
201 return cachingHashMap.containsKey(key) && !isExpired(cachingHashMap.get(key));
202 }
203
204 @Override
205 public boolean containsValue(Object value) {
206 for (Timestamped<V> val : cachingHashMap.values()) {
207 if (val.getValue().equals(value)) {
208 if (!isExpired(val)) {
209 return true;
210 }
211 }
212 }
213 return false;
214 }
215
216 private boolean isExpired(Timestamped<V> stamped) {
217 if ((expireAfterAccess == UNSET_INT) && (expireAfterWrite == UNSET_INT)) {
218 return false;
219 }
220
221 boolean expireWrite = (stamped.getWriteTimestamp() + expireAfterWrite <= currentTimeNanos());
222 boolean expireAccess = (stamped.getAccessTimestamp() + expireAfterAccess <= currentTimeNanos());
223
224 if (expireAfterAccess == UNSET_INT) {
225 return expireWrite;
226 }
227 if (expireAfterWrite == UNSET_INT) {
228 return expireAccess;
229 }
230
231 return expireWrite || expireAccess;
232 }
233
234 private long currentTimeNanos() {
235 return ticker.read();
236 }
237
238 private void alertListenerIfPresent(Object key, Object value, RemovalCause cause) {
239 if (removalListener != null) {
240 removalListener.onRemoval(new RemovalNotification(key, value, cause));
241 }
242 }
243
244 private V load(Object key) throws ExecutionException {
245 long startTime = ticker.read();
246 V calculatedValue;
247 try {
248
249
250
251
252
253
254
255
256
257 K castKey = (K) key;
258 calculatedValue = loader.load(castKey);
259 put(castKey, calculatedValue);
260 } catch (RuntimeException e) {
261 statsCounter.recordLoadException(ticker.read() - startTime);
262 throw new UncheckedExecutionException(e);
263 } catch (Exception e) {
264 statsCounter.recordLoadException(ticker.read() - startTime);
265 throw new ExecutionException(e);
266 } catch (Error e) {
267 statsCounter.recordLoadException(ticker.read() - startTime);
268 throw new ExecutionError(e);
269 }
270
271 if (calculatedValue == null) {
272 String message = loader + " returned null for key " + key + ".";
273 throw new CacheLoader.InvalidCacheLoadException(message);
274 }
275 statsCounter.recordLoadSuccess(ticker.read() - startTime);
276 return calculatedValue;
277 }
278
279 private V getIfPresent(Object key) {
280 key = checkNotNull(key);
281 Timestamped<V> value = cachingHashMap.get(key);
282
283 if (value == null) {
284 return null;
285 } else if (!isExpired(value)) {
286 value.updateTimestamp();
287 return value.getValue();
288 } else {
289 alertListenerIfPresent(key, value.getValue(), RemovalCause.EXPIRED);
290 cachingHashMap.remove(key);
291 return null;
292 }
293 }
294
295 private V getOrLoad(K key) throws ExecutionException{
296 V value = get(key);
297 if (value != null) {
298 return value;
299 }
300 return load(key);
301 }
302
303 private static class Timestamped<V> {
304 private final V value;
305 private final Ticker ticker;
306 private long writeTimestamp;
307 private long accessTimestamp;
308
309 public Timestamped(V value, Ticker ticker) {
310 this.value = checkNotNull(value);
311 this.ticker = checkNotNull(ticker);
312 this.writeTimestamp = ticker.read();
313 this.accessTimestamp = this.writeTimestamp;
314 }
315
316 public V getValue() {
317 return value;
318 }
319
320 public void updateTimestamp() {
321 accessTimestamp = ticker.read();
322 }
323
324 public long getAccessTimestamp() {
325 return accessTimestamp;
326 }
327
328 public long getWriteTimestamp() {
329 return writeTimestamp;
330 }
331
332 public boolean equals(Object o) {
333 return value.equals(o);
334 }
335
336 public int hashCode() {
337 return value.hashCode();
338 }
339 }
340
341
342
343
344
345
346
347 public static class LocalManualCache<K, V> extends AbstractCache<K, V> {
348 final LocalCache<K, V> localCache;
349
350 LocalManualCache(CacheBuilder<? super K, ? super V> builder) {
351 this(builder, null);
352 }
353
354 protected LocalManualCache(CacheBuilder<? super K, ? super V> builder,
355 CacheLoader<? super K, V> loader) {
356 this.localCache = new LocalCache<K, V>(builder, loader);
357 }
358
359
360
361 @Override
362 public V get(K key, Callable<? extends V> valueLoader) throws ExecutionException {
363 V value = localCache.get(key);
364 if (value != null) {
365 return value;
366 }
367
368 try {
369 V newValue = valueLoader.call();
370 localCache.put(key, newValue);
371 return newValue;
372 } catch (Exception e) {
373 throw new ExecutionException(e);
374 }
375 }
376
377 @Override
378 @Nullable
379 public V getIfPresent(Object key) {
380 return localCache.getIfPresent(key);
381 }
382
383 @Override
384 public void put(K key, V value) {
385 localCache.put(key, value);
386 }
387
388 @Override
389 public void invalidate(Object key) {
390 key = checkNotNull(key);
391 localCache.remove(key);
392 }
393
394 @Override
395 public void invalidateAll() {
396 localCache.clear();
397 }
398
399 @Override
400 public long size() {
401 return localCache.size();
402 }
403
404 @Override
405 public ConcurrentMap<K, V> asMap() {
406 return localCache;
407 }
408 }
409
410
411
412
413
414
415
416 public static class LocalLoadingCache<K, V>
417 extends LocalManualCache<K, V> implements LoadingCache<K, V> {
418
419 LocalLoadingCache(CacheBuilder<? super K, ? super V> builder,
420 CacheLoader<? super K, V> loader) {
421 super(builder, checkNotNull(loader));
422 }
423
424
425
426 @Override
427 public V get(K key) throws ExecutionException {
428 return localCache.getOrLoad(key);
429 }
430
431 @Override
432 public V getUnchecked(K key) {
433 try {
434 return get(key);
435 } catch (ExecutionException e) {
436 throw new UncheckedExecutionException(e.getCause());
437 }
438 }
439
440 @Override
441 public final V apply(K key) {
442 return getUnchecked(key);
443 }
444
445 @Override
446 public ImmutableMap<K, V> getAll(Iterable<? extends K> keys) throws ExecutionException {
447 Map<K, V> map = new HashMap<K, V>();
448 for (K key : keys) {
449 map.put(key, localCache.getOrLoad(key));
450 }
451 return ImmutableMap.copyOf(map);
452 }
453
454 @Override
455 public void refresh(K key) {
456 throw new UnsupportedOperationException();
457 }
458 }
459
460
461
462
463
464
465
466
467 private class CapacityEnforcingLinkedHashMap<K, V> extends LinkedHashMap<K, Timestamped<V>> {
468
469 private final StatsCounter statsCounter;
470 private final RemovalListener removalListener;
471 private final long maximumSize;
472
473 public CapacityEnforcingLinkedHashMap(
474 int initialCapacity,
475 float loadFactor,
476 boolean accessOrder,
477 long maximumSize,
478 StatsCounter statsCounter,
479 @Nullable RemovalListener removalListener) {
480 super(initialCapacity, loadFactor, accessOrder);
481 this.maximumSize = maximumSize;
482 this.statsCounter = statsCounter;
483 this.removalListener = removalListener;
484 }
485
486 @Override
487 protected boolean removeEldestEntry(Map.Entry<K, Timestamped<V>> ignored) {
488 boolean removal = (maximumSize == UNSET_INT) ? false : (size() > maximumSize);
489 if ((removalListener != null) && removal) {
490 removalListener.onRemoval(new RemovalNotification(
491 ignored.getKey(),
492 ignored.getValue().getValue(),
493 RemovalCause.SIZE));
494 }
495 statsCounter.recordEviction();
496 return removal;
497 }
498 }
499
500
501
502
503
504 enum Strength {
505
506
507
508
509
510 STRONG {
511 @Override
512 Equivalence<Object> defaultEquivalence() {
513 return Equivalence.equals();
514 }
515 },
516
517 SOFT {
518 @Override
519 Equivalence<Object> defaultEquivalence() {
520 return Equivalence.identity();
521 }
522 },
523
524 WEAK {
525 @Override
526 Equivalence<Object> defaultEquivalence() {
527 return Equivalence.identity();
528 }
529 };
530
531 abstract Equivalence<Object> defaultEquivalence();
532 }
533
534
535
536
537
538
539
540 class EntryIterator implements Iterator<Entry<K, V>> {
541 Iterator<Entry<K, Timestamped<V>>> iterator;
542 Entry<K, Timestamped<V>> lastEntry;
543 Entry<K, Timestamped<V>> nextEntry;
544
545 EntryIterator() {
546 this.iterator = LocalCache.this.cachingHashMap.entrySet().iterator();
547 }
548
549 @Override
550 public Entry<K, V> next() {
551 if (nextEntry == null) {
552 hasNext();
553
554 if (nextEntry == null) {
555 throw new NoSuchElementException();
556 }
557 }
558
559 lastEntry = nextEntry;
560 nextEntry = null;
561 return new WriteThroughEntry(lastEntry.getKey(), lastEntry.getValue().getValue());
562 }
563
564 @Override
565 public boolean hasNext() {
566 if (nextEntry == null) {
567 while (iterator.hasNext()) {
568 Entry<K, Timestamped<V>> next = iterator.next();
569 if (!isExpired(next.getValue())) {
570 nextEntry = next;
571 return true;
572 }
573 }
574 return false;
575 }
576 return true;
577 }
578
579 @Override
580 public void remove() {
581 checkState(lastEntry != null);
582 LocalCache.this.remove(lastEntry.getKey(), lastEntry.getValue());
583 lastEntry = null;
584 }
585 }
586
587
588
589
590 final class KeyIterator implements Iterator<K> {
591 private EntryIterator iterator;
592
593 KeyIterator() {
594 iterator = new EntryIterator();
595 }
596
597 @Override
598 public boolean hasNext() {
599 return iterator.hasNext();
600 }
601
602 @Override
603 public K next() {
604 return iterator.next().getKey();
605 }
606
607 @Override
608 public void remove() {
609 iterator.remove();
610 }
611 }
612
613
614
615
616 final class ValueIterator implements Iterator<V> {
617 private EntryIterator iterator;
618
619 ValueIterator() {
620 iterator = new EntryIterator();
621 }
622
623 @Override
624 public boolean hasNext() {
625 return iterator.hasNext();
626 }
627
628 @Override
629 public V next() {
630 return iterator.next().getValue();
631 }
632
633 @Override
634 public void remove() {
635 iterator.remove();
636 }
637 }
638
639 Set<K> keySet;
640
641 @Override
642 public Set<K> keySet() {
643
644 Set<K> ks = keySet;
645 return (ks != null) ? ks : (keySet = new KeySet(this));
646 }
647
648 Collection<V> values;
649
650 @Override
651 public Collection<V> values() {
652
653 Collection<V> vs = values;
654 return (vs != null) ? vs : (values = new Values(this));
655 }
656
657 Set<Entry<K, V>> entrySet;
658
659 @Override
660 public Set<Entry<K, V>> entrySet() {
661
662 Set<Entry<K, V>> es = entrySet;
663 return (es != null) ? es : (entrySet = new EntrySet(this));
664 }
665
666
667
668
669
670 private final class WriteThroughEntry implements Entry<K, V> {
671 final K key;
672 V value;
673
674 WriteThroughEntry(K key, V value) {
675 this.key = checkNotNull(key);
676 this.value = checkNotNull(value);
677 }
678
679 @Override
680 public K getKey() {
681 return key;
682 }
683
684 @Override
685 public V getValue() {
686 return value;
687 }
688
689 @Override
690 public boolean equals(@Nullable Object object) {
691
692 if (object instanceof Entry) {
693 Entry<?, ?> that = (Entry<?, ?>) object;
694 return key.equals(that.getKey()) && value.equals(that.getValue());
695 }
696 return false;
697 }
698
699 @Override
700 public int hashCode() {
701
702 return key.hashCode() ^ value.hashCode();
703 }
704
705 @Override
706 public V setValue(V newValue) {
707 throw new UnsupportedOperationException();
708 }
709
710
711
712
713 @Override
714 public String toString() {
715 return getKey() + "=" + getValue();
716 }
717 }
718
719
720
721
722 abstract class AbstractCacheSet<T> extends AbstractSet<T> {
723 final ConcurrentMap<?, ?> map;
724
725 AbstractCacheSet(ConcurrentMap<?, ?> map) {
726 this.map = map;
727 }
728
729 @Override
730 public int size() {
731 return map.size();
732 }
733
734 @Override
735 public boolean isEmpty() {
736 return map.isEmpty();
737 }
738
739 @Override
740 public void clear() {
741 map.clear();
742 }
743 }
744
745
746
747
748 private final class KeySet extends AbstractCacheSet<K> {
749
750 KeySet(ConcurrentMap<?, ?> map) {
751 super(map);
752 }
753
754 @Override
755 public Iterator<K> iterator() {
756 return new KeyIterator();
757 }
758
759 @Override
760 public boolean contains(Object o) {
761 return map.containsKey(o);
762 }
763
764 @Override
765 public boolean remove(Object o) {
766 return map.remove(o) != null;
767 }
768 }
769
770
771
772
773 private final class Values extends AbstractCacheSet<V> {
774
775 Values(ConcurrentMap<?, ?> map) {
776 super(map);
777 }
778
779 @Override
780 public Iterator<V> iterator() {
781 return new ValueIterator();
782 }
783
784 @Override
785 public boolean contains(Object o) {
786 return map.containsValue(o);
787 }
788 }
789
790
791
792
793 private final class EntrySet extends AbstractCacheSet<Entry<K, V>> {
794
795 EntrySet(ConcurrentMap<?, ?> map) {
796 super(map);
797 }
798
799 @Override
800 public Iterator<Entry<K, V>> iterator() {
801 return new EntryIterator();
802 }
803
804 @Override
805 public boolean contains(Object o) {
806 if (!(o instanceof Entry)) {
807 return false;
808 }
809 Entry<?, ?> e = (Entry<?, ?>) o;
810 Object key = e.getKey();
811 if (key == null) {
812 return false;
813 }
814 V v = LocalCache.this.get(key);
815
816 return (v != null) && e.getValue().equals(v);
817 }
818
819 @Override
820 public boolean remove(Object o) {
821 if (!(o instanceof Entry)) {
822 return false;
823 }
824 Entry<?, ?> e = (Entry<?, ?>) o;
825 Object key = e.getKey();
826 return (key != null) && LocalCache.this.remove(key, e.getValue());
827 }
828 }
829 }